The problem can be found at the following link: Question Link
For this problem, I utilized a sliding window approach. Here are the steps:
- Initialize variables
nax
,i
,j
, andout
. - Iterate through the string
s
using two pointersi
andj
. - Within the loop, create substrings of
s
starting from indexi
and ending at indexj
. - Check if the length of the current substring is greater than
nax
and if the substring repeats later in the string. - Update
nax
andout
accordingly. - Slide the window by incrementing
i
orj
based on the condition. - Return the longest repeating and non-overlapping substring.
- Time Complexity:
O(n^2)
, where n is the length of the input string. This complexity arises from generating all possible substrings and checking for repeats. - Auxiliary Space Complexity:
O(1)
, as we are not using any extra space that grows with the input size.
class Solution {
public:
string longestSubstring(string s, int n) {
int nax = 0, i = 0, j = 0;
string out = "-1";
for( ; i < n && j < n; ++j) {
string str = s.substr(i, j - i + 1);
if (nax < str.size() && s.find(str, j + 1) != string::npos) {
nax = str.size();
out = str;
} else
++i;
}
return out;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.